package lc.q250_300;

/**
 * 给你一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。
 *
 * 你必须设计并实现线性时间复杂度的算法且仅使用常量额外空间来解决此问题。
 */
public class Q260 {

    public int[] singleNumber(int[] nums) {
        // 如果只有一个数，用xor即可，现在并不是一个
        int xor = 0;
        for (int num : nums) {
            xor ^= num;
        }
        // xor等于两个数的抑或结果
        // 找出xor的最低位1，这样的话，以该为0和1分成两组数，最后剩的两数肯定分别在两组里，而相同的会在同一组，这样就能抵消
        int lsb = Integer.MAX_VALUE == xor ? xor: xor & (-xor);
        int type1 = 0, type2= 0;
        for (int num : nums) {
            if ((num & lsb) == 0) {
                type1 ^= num;
            } else {
                type2 ^= num;
            }
        }
        return new int[]{type1, type2};
    }
}
